/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


 /**

 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2
示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/successor-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


 如果 结点node有右子节点，那么后继者是右子节点 一直向 左结点遍历的最后结点
 如果结点node没有右子节点，但他本身作为其父节点的左子节点，，则后继者就是父节点
 如果结点node没有右子节点，但他本身作为其父节点的右子节点，，则后继者就是第一个左父节点
  */
class Solution {
public:
   //一直向左结点遍历
    TreeNode*  travelAlongLeft( TreeNode* p)
    {
        while(p)
        {
            if(p->left)
            {
                p = p->left;
            }
            else
            {
                return p;
            }
        }
        return 0;
    }
    TreeNode * back_Parent( TreeNode* p ,vector<TreeNode*>& parents)
    {
        for(int i = parents.size()-1;i>=0;i--)
        {
            if(parents[i]->right == p)
            {
                p = parents[i];
            }
            else
            {
                return  parents[i];
            }
        }
        return 0;
    }
    TreeNode* inorderSuccessorHelper(TreeNode* root, TreeNode* p ,vector<TreeNode*>& parents)
    {
        if(root == 0)
            return 0;
        if(root == p)
        {
            if(parents[parents.size()-1]->left == p)
                return parents[parents.size()-1];
            else
            {
                return back_Parent(  p , parents);
            }
               
        }  
        if(p->val > root->val)
        {
            parents.push_back(root);
            return inorderSuccessorHelper(root->right,  p , parents);
        } 
        else 
        {
            parents.push_back(root);
            return inorderSuccessorHelper(root->left,  p , parents);
        }
    } 

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) 
    {
        if(p->right)
            return travelAlongLeft(p->right);
        
        if(root == p)
            return 0;
        
        vector<TreeNode* > parents;
        return inorderSuccessorHelper(root,p ,parents);
    }
};